//
// Created by lh on 17-9-5.
//

#include "iostream"
#include "algorithm"
using namespace std;

int e[50][50];
int book[50];
int dis[50];
int n,m,start;
int main()
{
    cin>>n>>m>>start;
    //初始化邻接矩阵
    for (int i = 1; i <=n ; ++i) {
        for (int j = 1; j <=n ; ++j) {
            if(i==j)
                e[i][j]=0;
            else
                e[i][j]=1e9;
        }
    }
    //对邻接矩阵赋值
    for (int t = 1; t <=m; ++t) {
        int t1,t2,t3;
        cin>>t1>>t2>>t3;
        e[t1][t2]=t3;
    }
    //初始化最短路径数组
    for (int k = 1; k <=n ; ++k) {
        dis[k]=e[start][k];
    }

    book[start]=1;
    for (int loop = 0; loop < n; ++loop) {

        int min_s=1e9;//min start
        int min_i=0;//min_index
        for (int t = 1; t <= n; ++t) {
            if(!book[t]&&dis[t]<min_s) {
                min_s = dis[t];
                min_i=t;
            }
        }
        book[min_i]=1;

        for (int j = 1; j <=n ; ++j) {
            if(!book[j])
                dis[j]=min(min_i,dis[min_i]+e[min_i][j]);
        }
    }

    for (int p = 1; p <=n ; ++p) {
        cout<<dis[p]<<" ";
    }
    cout<<endl;
    return 0;
}
/*
6 9 1
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 12
4 6 15
5 6 4
 * */